#include<iostream>
#include<vector>
using namespace std;

void BubbleSort(vector<int>& a)
{
	int n = a.size();
	for(int i = 0;i<n-1;i++) //n个数,只需要排序n-1趟
	{
		for(int j = 0;j<n-i-1;j++) //每一轮少比较一个数 ,第一轮只需比较到n-2位置, j+1就是最后一个元素
		{
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
		}
	}
}


void BubbleSort2(vector<int>& a)
{
	int n = a.size();
	for(int i = 0;i<n-1;i++) //n个数,只需要排序n-1趟
	{
		bool flag = true; //已经有序了
		for(int j = 0;j<n-i-1;j++) //每一轮少比较一个数 
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
				flag  = false;
			}
		}
		if(flag)
			break;	
	}
}
int partion1(vector<int>& a,int left,int right)
{
	int key = left;
	while(left < right)
	{
		//右边先走->找比key对应的值严格小的
		while(left < right && a[right] >= a[key])
		{
			right--;
		}
		while(left < right && a[left] <= a[key])
		{
			left++;
		}
		swap(a[left],a[right]);
 	}
	swap(a[key],a[left]);
	return left;
}
void QuickSort(vector<int>& a,int left,int right)
{
	if(left >= right)
		return ;
	int key = partion1(a,left,right);
	//[left,key-1] key [key+1,right]
	QuickSort(a,left,key-1);
	QuickSort(a,key+1,right);
}
int main()
{
	vector<int> a {9,8,7,6,5,4,3,2,1,13,2,1,2,3,4};
	QuickSort(a,0,a.size()-1);
	for(auto& x: a)
		cout << x <<" ";
	cout << endl;
	return 0;
}
